package stack;

import java.util.*;

public class QuestionOne {
    /*给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

*/
    public boolean isValid(String s) {
        if (s.length() == 1)return false;
        HashMap<Character, Character> signMap = new HashMap<>();
        signMap.put('}','{');
        signMap.put(']','[');
        signMap.put(')','(');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (signMap.containsKey(s.charAt(i))){
                if (stack.isEmpty() || stack.peek() != signMap.get(s.charAt(i))){
                    return false;
                }
                stack.pop();
            }else{
                stack.push(s.charAt(i));
            }
        }
        return stack.isEmpty();
    }
    public boolean isValid1(String s) {
      int len = s.length();
      if (len % 2 ==1)return false;
        HashMap<Character, Character> map = new HashMap<>();
        map.put('{','}');
        map.put('[',']');
        map.put('(',')');

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)){
                //如果是左 push
                stack.push(ch);
            }else{
                if (stack.isEmpty() || stack.peek()!= map.get(ch)){
                    return false;
                }
                stack.pop();
            }
        }
        return map.isEmpty();
    }



}
